package LC;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode.com/problems/palindrome-partitioning/description/
 * Given a string s, partition s such that every substring of the partition is a palindrome.
 * Return all possible palindrome partitioning of s.
 * For example, given s = "aab",
 * Return
 * [
 * ["aa","b"],
 * ["a","a","b"]
 * ]
 */
public class LC_131_PalindromePartitioning_DFS_BackTracking {
    public static void main(String[] args) {
        List<List<String>> lists = Solution.partition("abcedde");
        System.out.println(lists);
    }

    static class Solution {

        static List<List<String>> partition(String s) {
            List<List<String>> result = new ArrayList<>();
            List<String> temp = new ArrayList<>();
            dfs(s, 0, temp, result);
            return result;
        }

        private static void dfs(String s, int curIndex, List<String> temp, List<List<String>> result) {
            if (curIndex == s.length()) {
                result.add(new ArrayList<>(temp));
                return;
            }
            for (int i = curIndex + 1; i <= s.length(); i++) {
                String prefix = s.substring(curIndex, i);
                if (!isPrlindrome(prefix))
                    continue;
                temp.add(prefix);
                dfs(s, i, temp, result);
                temp.remove(temp.size() - 1);
            }
        }

        private static boolean isPrlindrome(String s) {
            int left = 0;
            int right = s.length() - 1;
            while (left < right) {
                if (s.charAt(left) != s.charAt(right))
                    return false;
                left++;
                right--;
            }
            return true;
        }

    }
}
